#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<unordered_map<int, int>>meme(nums.size());
        return dfs(nums, target, 0, 0, meme);
    }
private:
    int dfs(vector<int>&nums,int target,int index,int current,vector<unordered_map<int,int>>&meme) {
        if(index==nums.size()){return current==target?1:0; }
        if (meme[index].find(current) != meme[index].end()) { return meme[index][current]; }
        int add = dfs(nums, target, index + 1, current + nums[index], meme);
        int sub = dfs(nums, target, index + 1, current - nums[index], meme);
        meme[index][current] = add + sub;
        return meme[index][current];
    }
};
